import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class ContainsDuplicateII {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // abs(i-j) <= k，说明重复元素距离最大为k，也就是求子串中是否存在重复元素
        // 思路：滑动窗口 + hash
        // 子串中是否存在重复元素, 并且重复元素之间的距离小于等于k
        // 即窗口中满足:拥有重复元素, 重复元素之间的距离小于等于k
        // 用 Set 来当窗口, 窗口大小设置为 k
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return true;
            }
            // 进窗口
            set.add(nums[i]);

            if(set.size() > k) { // 让 Set 里面的元素维持在 k 个
                // 出窗口
                set.remove(nums[i - k]);
            }
        }
        return false;
    }

    public boolean containsNearbyDuplicate1(int[] nums, int k) {
        // 哈希表 key 表示元素值, value 表示当前元素的下标
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])) {
                if(i - map.get(nums[i]) <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);
        }
        return false;
    }
}
